package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/">具有所有最深节点的最小子树(Smallest Subtree with all the Deepest Nodes)</a>
 * <p>给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。</p>
 * <p>返回包含原始树中所有最深节点的最小子树 。</p>
 * <p>如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。</p>
 * <p>一个节点的 子树 是该节点加上它的所有后代的集合。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,5,1,6,2,0,8,null,null,7,4]
 *                       3
 *                     /   \
 *                    5     1
 *                   / \   / \
 *                  6   <a color="red">2</a> 0   8
 *                     / \
 *                    <a color="blue">7</a>   <a color="blue">4</a>
 *      输出：[2,7,4]
 *      解释：
 *          我们返回值为 2 的节点，在图中用红色标记。
 *          在图中用蓝色标记的是树的最深的节点。
 *          注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。
 * 示例 2：
 *      输入：root = [1]
 *      输出：[1]
 *      解释：根节点是树中最深的节点。
 *
 * 示例 3：
 *      输入：root = [0,1,3,null,2]
 *                          0
 *                         / \
 *                        1   3
 *                         \
 *                          2
 *      输出：[2]
 *      解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>树中节点的数量在 [1, 500] 范围内。</li>
 *      <li>0 <= Node.val <= 500</li>
 *      <li>每个节点的值都是 独一无二 的。</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @see LC0865SmallestSubtreeWithAllTheDeepestNodes_M 具有所有最深节点的最小子树(Smallest Subtree with all the Deepest Nodes)
 * @see LC1123LowestCommonAncestorOfDeepestLeaves_M 最深叶节点的最近公共祖先(Lowest Common Ancestor of Deepest Leaves)
 * @since 2023/5/25 14:05
 */
public class LC0865SmallestSubtreeWithAllTheDeepestNodes_M {

    static class Solution {
        /**
         * // 求最深节点的公共父节点
         */
        public TreeNode subtreeWithAllDeepest(TreeNode root) {
            int leftTreeMaxDepth = getMaxDepth(root.left);
            int rightTreeMaxDepth = getMaxDepth(root.right);
            // 如果左子树最大深度与右子树最大深度相等：说明当前节点是最深的
            if (leftTreeMaxDepth == rightTreeMaxDepth) {
                return root;
            }
            // 如果左子树的深度 大于 右子树的深度 ，说明最深的节点在左子树上；在左子树上继续查找
            // 如果左子树的深度 小于 右子树的深度 ，说明最深的节点在右子树上；在右子树上继续查找
            return leftTreeMaxDepth > rightTreeMaxDepth ? subtreeWithAllDeepest(root.left) : subtreeWithAllDeepest(root.right);
        }

        /**
         * 获取以当前节点为根的树的最大深度
         */
        private int getMaxDepth(TreeNode currNode) {
            if (currNode == null) {
                return 0;
            }
            return Math.max(getMaxDepth(currNode.left), getMaxDepth(currNode.right)) + 1;
        }
    }
}
